#ifndef GRAPH_UTILS_HPP
#define GRAPH_UTILS_HPP

#include <climits>

#include <include/graph.hpp>

typedef std::vector<Vertex*>::const_iterator vec_c_vertex;
typedef std::vector<Vertex*> * listOfVerticesPtr;

class GraphUtils {

public:
    static int computeGraphsDiameter(Graph * graph) {
        int graphsDiameter = -1;

        listOfVerticesPtr listOfVertices = graph->getListOfVertices();
        vec_c_vertex endOfListOfVertices = listOfVertices->end();

        int tmpDiameter = 0;
        for(vec_c_vertex iter = listOfVertices->begin();
            iter != endOfListOfVertices; ++iter) {

            tmpDiameter = runBFS(graph, (*iter));

            if(tmpDiameter > graphsDiameter) {
                graphsDiameter = tmpDiameter;
            }
        }
        graph->setGraphsDiameter(graphsDiameter);
	
        return graphsDiameter;
    }

private:
  
    static int runBFS(Graph * graph, Vertex * start) {
        int maxDistance = 0;
        std::vector<Vertex*> * listOfSeenVertices = new std::vector<Vertex*>();
        runInitialization(graph, start, listOfSeenVertices);

        bool unseenNeighbourFound = true;
        while(!listOfSeenVertices->empty()) {
            Vertex * actualVertex = listOfSeenVertices->back();
            listOfSeenVertices->pop_back();
            actualVertex->setState(Vertex::DONE);

            vec_c_vertex endOfNeighbours = actualVertex->getNeighbours()->end();
            for(vec_c_vertex neighbour = actualVertex->getNeighbours()->begin();
                neighbour != endOfNeighbours; ++neighbour) {

                if((*neighbour)->getState() == Vertex::UNSEEN) {
                    (*neighbour)->setState(Vertex::SEEN);
                    listOfSeenVertices->push_back((*neighbour));
                    if(unseenNeighbourFound) {
                        maxDistance++;
                        unseenNeighbourFound = false;
                    }
                }
            }
            unseenNeighbourFound = true;
        }

        return maxDistance;
    }

    static void runInitialization(Graph * graph, Vertex * start,
                                  listOfVerticesPtr unseenVertices) {
        unseenVertices->push_back(start);
        start->setState(Vertex::SEEN);

        vec_c_vertex end = graph->getListOfVertices()->end();
        for(vec_c_vertex iter = graph->getListOfVertices()->begin();
            iter != end; ++iter) {

            (*iter)->setState(Vertex::UNSEEN);
        }

    }

};

#endif // GRAPH_UTILS_HPP
